The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer and to structures and techniques for facilitating non-blocking implementations of shared data structures. Non-blocking data structures and mechanisms are desirable because they overcome many of the common problems associated with the use of mutual exclusion (locks) for coordination between concurrent threads. To avoid these problems, such mechanisms and data structures typically must ensure that the delay or failure of some set of threads does not prevent progress by other threads.
Traditionally in the research literature, non-blocking data structures and mechanisms are also required to ensure progress by the participating threads, and the strength of this requirement has been formalized in properties such as wait-freedom and lock-freedom. As typically understood, wait-freedom requires that every thread makes progress in a finite number of its own steps, regardless of the timing behavior of other threads. Lock-freedom, a weaker condition, requires that after a finite number of steps of one thread, some thread has made progress. In the context of non-blocking data structures, “making progress” usually means completing an operation.
Designing algorithms that both behave correctly and ensure progress (according to progress conditions such as those mentioned above) for all interleavings of the threads' steps is very challenging. Ensuring progress often necessitates the use of complicated and computationally expensive “helping mechanisms,” whereby a thread that potentially interferes with another thread's progress can subsequently “help” that thread to make progress. Largely as a result of this complication and expense, very few non-blocking mechanisms are actually deployed in practice. Therefore, as a practical matter, given the current state of the art, system and application designers must still use locks and must therefore deal with all of the problems associated with them.
Accordingly, alternative techniques are desired whereby at least some of the complexities and related computational expense of prior techniques may be avoided or reduced. In this way, non-blocking shared data objects may achieve wider adoption and use.